#include "TexturePacker.h"
#include <assert.h>

#pragma warning(disable:4100 4244)

namespace TEXTURE_PACKER
{


	class Rect
	{
	public:

		void set(int x1,int y1,int x2,int y2)
		{
			mX1 = x1;
			mY1 = y1;
			mX2 = x2;
			mY2 = y2;
		}

		bool intersects(const Rect &r) const
		{
			bool intersect = true;

			if ( mX2 < r.mX1 ||
				mX1 > r.mX2 ||
				mY2 < r.mY1 ||
				mY1 > r.mY2 )
			{
				intersect  = false;
			}
			return intersect;
		}
		int mX1;
		int mY1;
		int mX2;
		int mY2;
	};

	class Texture
	{
	public:
		void set(int wid,int hit)
		{
			mWidth = wid;
			mHeight = hit;
			mX = 0;
			mY = 0;
			mFlipped = false;
			mPlaced = false;
			mArea = wid*hit;
			if ( wid >= hit )
				mLongestEdge = wid;
			else
				mLongestEdge = hit;
		}

		bool isPlaced(void) const { return mPlaced; };

		void place(int x,int y,bool flipped)
		{
			mX = x;
			mY = y;
			mFlipped = flipped;
			mPlaced = true;
		}

		int mWidth;
		int mHeight;
		int mX;
		int mY;
		int mLongestEdge;
		int mArea;

		bool  mFlipped:1;       // true if the texture was rotated to make it fit better.
		bool  mPlaced:1;
	};

	class Node
	{
	public:
		Node(int x,int y,int wid,int hit)
		{
			mX = x;
			mY = y;
			mWidth = wid;
			mHeight = hit;
			mNext = 0;
		}

		Node *getNext(void) const { return mNext; };

		bool fits(int wid,int hit,int &edgeCount) const
		{
			bool ret = false;

			edgeCount = 0;

			if ( wid == mWidth  || hit == mHeight || wid == mHeight || hit == mWidth )
			{
				if ( wid == mWidth )
				{
					edgeCount++;
					if ( hit == mHeight )
						edgeCount++;
				}
				else if ( wid == mHeight )
				{
					edgeCount++;
					if ( hit == mWidth )
					{
						edgeCount++;
					}
				}
				else if ( hit == mWidth )
				{
					edgeCount++;
				}
				else if ( hit == mHeight )
				{
					edgeCount++;
				}
			}

			if ( wid <= mWidth && hit <= mHeight )
			{
				ret = true;
			}
			else if ( hit <= mWidth && wid <= mHeight )
			{
				ret = true;
			}

			return ret;
		}

		void getRect(Rect &r) const
		{
			r.set(mX,mY,mX+mWidth-1,mY+mHeight-1);
		}

		void validate(Node *n)
		{
			Rect r1;
			Rect r2;
			getRect(r1);
			n->getRect(r2);
			assert( !r1.intersects(r2) );
		}

		bool merge(const Node &n)
		{
			bool ret = false;

			Rect r1;
			Rect r2;

			getRect(r1);
			n.getRect(r2);
			r1.mX2++;
			r1.mY2++;
			r2.mX2++;
			r2.mY2++;

			// if we share the top edge then..
			if ( r1.mX1 == r2.mX1 && r1.mX2 == r2.mX2 && r1.mY1 == r2.mY2 )
			{
				mY = n.mY;
				mHeight+=n.mHeight;
				ret = true;
			}
			else if ( r1.mX1 == r2.mX1 && r1.mX2 == r2.mX2 && r1.mY2 == r2.mY1 ) // if we share the bottom edge
			{
				mHeight+=n.mHeight;
				ret = true;
			}
			else if ( r1.mY1 == r2.mY1 && r1.mY2 == r2.mY1 && r1.mX1 == r2.mX2 ) // if we share the left edge
			{
				mX = n.mX;
				mWidth+=n.mWidth;
				ret = true;
			}
			else if ( r1.mY1 == r2.mY1 && r1.mY2 == r2.mY1 && r1.mX2 == r2.mX1 ) // if we share the left edge
			{
				mWidth+=n.mWidth;
				ret = true;
			}

			return ret;
		}


		Node *mNext;
		int mX;
		int mY;
		int mWidth;
		int mHeight;
	};

	class MyTexturePacker : public TexturePacker
	{
	public:
		MyTexturePacker(void)
		{
			mTextureCount = 0;
			mTextures = 0;
			mLongestEdge = 0;
			mTotalArea = 0;
			mTextureIndex = 0;
			mFreeList = 0;
		}
		~MyTexturePacker(void)
		{
			reset();
		}

		void reset(void)
		{
			mTextureCount = 0;
			delete []mTextures;
			mTextures = 0;
			mLongestEdge = 0;
			mTotalArea = 0;
			mTextureIndex = 0;
			if ( mFreeList )
			{
				Node *next = mFreeList;
				while ( next )
				{
					Node *kill = next;
					next = next->getNext();
					delete kill;
				}
			}
		}

		virtual void  setTextureCount(int tcount) // number of textures to consider..
		{
			reset();
			mTextureCount = tcount;
			mTextures = new Texture[tcount];
		}

		virtual void  addTexture(int wid,int hit)  // add textures 0 - n
		{
			assert( mTextureIndex < mTextureCount );
			if ( mTextureIndex < mTextureCount )
			{
				mTextures[mTextureIndex].set(wid,hit);
				mTextureIndex++;
				if ( wid > mLongestEdge )  mLongestEdge = wid;
				if ( hit > mLongestEdge )  mLongestEdge = hit;
				mTotalArea+=(wid*hit);
			}
		}

		virtual void newFree(int x,int y,int wid,int hit)
		{
			Node *node = new Node(x,y,wid,hit);
			node->mNext = mFreeList;
			mFreeList = node;
		}

		int nextPow2(int v) const
		{
			int p = 1;
			while ( p < v )
			{
				p = p*2;
			}
			return p;
		}

		virtual int packTextures(int &width,int &height,const options_t & options)  // pack the textures, the return code is the amount of wasted/unused area.
		{
			width = 0;
			height = 0;

			if ( options.onePixelBorder )
			{
				for (int i=0; i<mTextureCount; i++)
				{
					Texture &t = mTextures[i];
					t.mWidth+=2;
					t.mHeight+=2;
				}
				mLongestEdge+=2;
			}

			if ( options.powerOfTwo )
			{
				mLongestEdge = nextPow2(mLongestEdge);
			}
			
			// The width is no more than the longest edge of any rectangle passed in
			width  = mLongestEdge > options.minWidth ? mLongestEdge : options.minWidth; 

			int count = mTotalArea / (mLongestEdge*mLongestEdge);
			height = (count+2)*mLongestEdge;            // We guess that the height is no more than twice the longest edge.  On exit, this will get shrunk down to the actual tallest height.

			mDebugCount = 0;
			newFree(0,0,width,height);

			// We must place each texture
			for (int i=0; i<mTextureCount; i++)
			{

				int index = 0;
				int longestEdge = 0;
				int mostArea = 0;

				// We first search for the texture with the longest edge, placing it first.
				// And the most area...
				for (int j=0; j<mTextureCount; j++)
				{

					Texture &t = mTextures[j];

					if ( !t.isPlaced() ) // if this texture has not already been placed.
					{
						if ( t.mLongestEdge > longestEdge )
						{
							mostArea = t.mArea;
							longestEdge = t.mLongestEdge;
							index = j;
						}
						else if ( t.mLongestEdge == longestEdge ) // if the same length, keep the one with the most area.
						{
							if ( t.mArea > mostArea )
							{
								mostArea = t.mArea;
								index = j;
							}
						}
					}
				}

				// For the texture with the longest edge we place it according to this criteria.
				//   (1) If it is a perfect match, we always accept it as it causes the least amount of fragmentation.
				//   (2) A match of one edge with the minimum area left over after the split.
				//   (3) No edges match, so look for the node which leaves the least amount of area left over after the split.
				Texture &t = mTextures[index];

				int leastY = 0x7FFFFFFF;
				int leastX = 0x7FFFFFFF;

				Node *previousBestFit = 0;
				Node *bestFit = 0;
				Node *previous = 0;
				Node *search = mFreeList;
				int edgeCount = 0;

				// Walk the singly linked list of free nodes
				// see if it will fit into any currently free space
				while ( search )
				{
					int ec;
					if ( search->fits(t.mWidth,t.mHeight,ec) ) // see if the texture will fit into this slot, and if so how many edges does it share.
					{
						if ( ec == 2 )
						{
							previousBestFit = previous;     // record the pointer previous to this one (used to patch the linked list)
							bestFit = search; // record the best fit.
							edgeCount = ec;
							break;
						}
						if ( search->mY < leastY )
						{
							leastY = search->mY;
							leastX = search->mX;
							previousBestFit = previous;
							bestFit = search;
							edgeCount = ec;
						}
						else if ( search->mY == leastY && search->mX < leastX )
						{
							leastX = search->mX;
							previousBestFit = previous;
							bestFit = search;
							edgeCount = ec;
						}
					}
					previous = search;
					search = search->mNext;
				}

				//assert( bestFit ); // we should always find a fit location!

				if ( bestFit )
				{
					validate();

					switch ( edgeCount )
					{
					case 0:
						if ( t.mLongestEdge <= bestFit->mWidth )
						{
							bool flipped = false;

							int wid = t.mWidth;
							int hit = t.mHeight;

							if ( hit > wid && ( options.allowRotationToFit ) )
							{
								wid = t.mHeight;
								hit = t.mWidth;
								flipped = true;
							}

							t.place(bestFit->mX,bestFit->mY,flipped); // place it.

							newFree(bestFit->mX,bestFit->mY+hit,bestFit->mWidth,bestFit->mHeight-hit);

							bestFit->mX+=wid;
							bestFit->mWidth-=wid;
							bestFit->mHeight = hit;
							validate();
						}
						else
						{

							assert( t.mLongestEdge <= bestFit->mHeight );

							bool flipped = false;

							int wid = t.mWidth;
							int hit = t.mHeight;

							if ( hit < wid && ( options.allowRotationToFit ) )
							{
								wid = t.mHeight;
								hit = t.mWidth;
								flipped = true;
							}

							t.place(bestFit->mX,bestFit->mY,flipped); // place it.

							newFree(bestFit->mX,bestFit->mY+hit,bestFit->mWidth,bestFit->mHeight-hit);

							bestFit->mX+=wid;
							bestFit->mWidth-=wid;
							bestFit->mHeight = hit;
							validate();
						}
						break;
					case 1:
						{
							if ( t.mWidth == bestFit->mWidth )
							{
								t.place(bestFit->mX,bestFit->mY,false);
								bestFit->mY+=t.mHeight;
								bestFit->mHeight-=t.mHeight;
								validate();
							}
							else if ( t.mHeight == bestFit->mHeight )
							{
								t.place(bestFit->mX,bestFit->mY,false);
								bestFit->mX+=t.mWidth;
								bestFit->mWidth-=t.mWidth;
								validate();
							}
							else if ( t.mWidth == bestFit->mHeight )
							{
								t.place(bestFit->mX,bestFit->mY,true);
								bestFit->mX+=t.mHeight;
								bestFit->mWidth-=t.mHeight;
								validate();
							}
							else if ( t.mHeight == bestFit->mWidth )
							{
								t.place(bestFit->mX,bestFit->mY,true);
								bestFit->mY+=t.mWidth;
								bestFit->mHeight-=t.mWidth;
								validate();
							}
						}
						break;
					case 2:
						{
							bool flipped = ( options.allowRotationToFit ) && ( t.mWidth != bestFit->mWidth || t.mHeight != bestFit->mHeight );
							t.place(bestFit->mX,bestFit->mY,flipped);
							if ( previousBestFit )
							{
								previousBestFit->mNext = bestFit->mNext;
							}
							else
							{
								mFreeList = bestFit->mNext;
							}
							delete bestFit;
							validate();
						}
						break;
					}
					while ( mergeNodes() ); // keep merging nodes as much as we can...
				}
			}

			height = 0;
			width = 0;
			for (int i=0; i<mTextureCount; i++)
			{
				Texture &t = mTextures[i];
				if ( options.onePixelBorder )
				{
					t.mWidth-=2;
					t.mHeight-=2;
					t.mX++;
					t.mY++;
				}
				int x = t.mX+t.mWidth;
				int y = t.mY+t.mHeight;
				if ( x > width )
					width = x;
				if ( y > height )
					height = y;
			}

			if ( options.powerOfTwo )
			{
				width = nextPow2(width);
				height = nextPow2(height);
			}

			return (width*height)-mTotalArea;
		}

		bool mergeNodes(void)
		{
			Node *f = mFreeList;
			while ( f )
			{
				Node *prev = 0;
				Node *c = mFreeList;
				while ( c )
				{
					if ( f != c )
					{
						if ( f->merge(*c) )
						{
							assert(prev);
							prev->mNext = c->mNext;
							delete c;
							return true;
						}
					}
					prev = c;
					c = c->mNext;
				}
				f = f->mNext;
			}
			return false;
		}

		void validate(void)
		{
#ifdef _DEBUG
			Node *f = mFreeList;
			while ( f )
			{
				Node *c = mFreeList;
				while ( c )
				{
					if ( f != c )
					{
						f->validate(c);
					}
					c = c->mNext;
				}
				f = f->mNext;
			}
#endif
		}

		virtual bool  getTextureLocation(int index,int &x,int &y,int &wid,int &hit)
		{
			bool ret = false;

			x = y = wid = hit = 0;

			assert( index < mTextureCount );
			if ( index < mTextureCount )
			{
				Texture &t = mTextures[index];
				x = t.mX;
				y = t.mY;
				if ( t.mFlipped )
				{
					wid = t.mHeight;
					hit = t.mWidth;
				}
				else
				{
					wid = t.mWidth;
					hit = t.mHeight;
				}
				ret = t.mFlipped;
			}

			return ret;
		}


	private:
		int    mDebugCount;
		Node    *mFreeList;
		int    mTextureIndex;
		int    mTextureCount;
		Texture *mTextures;
		int    mLongestEdge;
		int    mTotalArea;
	};


	TexturePacker * createTexturePacker(void)
	{
		MyTexturePacker *m = new MyTexturePacker;
		return static_cast< TexturePacker *>(m);
	}

	void            releaseTexturePacker(TexturePacker *tp)
	{
		MyTexturePacker *m = static_cast< MyTexturePacker *>(tp);
		delete m;
	}

}; // end of namepsace
